package com.ly.algorithm.leetcode.tree;

import java.util.*;

/**
 * @Classname Problem501
 * @Description
 * 给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
 *
 * 假定 BST 有如下定义：
 *
 * 结点左子树中所含结点的值小于等于当前结点的值
 * 结点右子树中所含结点的值大于等于当前结点的值
 * 左子树和右子树都是二叉搜索树
 * 例如：
 * 给定 BST [1.txt,null,2,2],
 *
 *    1.txt
 *     \
 *      2
 *     /
 *    2
 * 返回[2].
 *
 * 提示：如果众数超过1个，不需考虑输出顺序
 *
 * 进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
 *
 * @Date 2020/9/24 14:53
 * @Author 冷心影翼
 */
public class Problem501 {
    public static void main(String[] args) {
        Solution501 solution501 = new Solution501();
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(2);
        root.right.left.right = new TreeNode(3);
        root.right.left.left = new TreeNode(3);
        int[] mode = solution501.findMode(root);
        System.out.println(Arrays.toString(mode));
    }
}


class Solution501 {
    private Map<Integer, Integer> map = new HashMap<>();

    public int[] findMode(TreeNode root) {
        preorder(root);
        int max = 0;
        List<Integer> res = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(entry.getValue()>max) {
                max = entry.getValue();
                res = new ArrayList<>();
                res.add(entry.getKey());
            }else if(entry.getValue() == max) {
                res.add(entry.getKey());
            }
        }
        int[] arr = new int[res.size()];
        int i =0;
        for(Integer r:res) {
            arr[i++] = r;
        }
        return arr;
    }

    public void preorder(TreeNode root) {
        if(root == null) {
            return;
        }
        map.put(root.val,map.containsKey(root.val)?map.get(root.val)+1:1);
        preorder(root.left);
        preorder(root.right);
    }
}
